package graph;

// 使用邻接表来表示图
public class GraphII {

    class GraphNode {
        int v;    //当前顶点的编号
        GraphNode next;

        public GraphNode() {
        }

        public GraphNode(int v) {
            this.v = v;
        }
    }

    int count = 0;    //顶点的个数
    int type;    //图的类型
    GraphNode[] lists;    //用以存储所有的链表结构

    //初始化图
    public GraphII(int n, int type) {
        count = n;
        lists = new GraphNode[n];
        this.type = type;
    }

    // 判断图的类型
    public int getType() {
        return type;
    }

    // 获取图的顶点数
    public int getVertexCount() {
        return count;
    }

    //插入边
    public void insertEdge(int u, int v) {
        for (int i = 0; i < count; i++) {
            if (lists[i].v == u) {
                GraphNode node = new GraphNode(v);
                node.next = lists[i].next;
                lists[i].next = node;
                break;
            }
        }
        //如果是无向图，那么我们还需要将v指向u
        if (type == 0) {
            for (int i = 0; i < count; i++) {
                if (lists[i].v == v) {
                    GraphNode node = new GraphNode(u);
                    node.next = lists[i].next;
                    lists[i].next = node;
                    break;
                }
            }
        }
    }

    //删除边
    public void deleteEdge(int u, int v) {
        for (int i = 0; i < count; i++) {
            if (lists[i].v == u) {
                GraphNode pre = lists[i];
                GraphNode cur = lists[i].next;
                while (cur != null && cur.v != v) {
                    pre = cur;
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur.next = null;
            }
        }
        //如果是无向图，那么我们还需要删除v指向u的边
        if (type == 0) {
            for (int i = 0; i < count; i++) {
                if (lists[i].v == v) {
                    GraphNode pre = lists[i];
                    GraphNode cur = lists[i].next;
                    while (cur != null && cur.v != u) {
                        pre = cur;
                        cur = cur.next;
                    }
                    pre.next = cur.next;
                    cur.next = null;
                }
            }
        }
    }

    //判断两个顶点是否相邻接
    public boolean isAdjacent(int u, int v) {
        for (int i = 0; i < count; i++) {
            if (lists[i].v == u) {
                GraphNode cur = lists[i];
                while (cur != null) {
                    if (cur.v != v) {
                        cur = cur.next;
                    } else {
                        return true;
                    }
                }
                break;
            }
        }
        return false;
    }

    //计算顶点的度
    public int getDegree(int u) {
        int degree = 0;
        //先计算单链表的长度
        //对于无向图，度即为单链表的长度
        for (int i = 0; i < count; i++) {
            if (lists[i].v == u) {
                GraphNode cur = lists[i];
                while (cur != null) {
                    degree++;
                    cur = cur.next;
                }
            }
        }
        //对于有向图，还需要遍历整个链表数组计算入度
        for (int i = 0; i < count; i++) {
            //不要从第一个开始，否则我们会将lists[u]的头结点计算在内
            GraphNode cur = lists[i].next;
            while (cur != null) {
                if (cur.v == u) {
                    degree++;
                    break;
                } else {
                    cur = cur.next;
                }
            }
        }
        return degree;
    }

    //计算入度
    public int getInDegree(int u) {
        int degree = 0;
        //计算单链表的长度
        for (int i = 0; i < count; i++) {
            if (lists[i].v == u) {
                GraphNode cur = lists[i];
                while (cur != null) {
                    degree++;
                    cur = cur.next;
                }
            }
        }
        return degree;
    }

    // 计算入度
    public int getOutDegree(int u) {
        int degree = 0;
        // 计算单链表的长度
        for (int i = 0; i < count; i++) {
            //不要从第一个开始，否则我们会将lists[u]的头结点计算在内
            GraphNode cur = lists[i].next;
            while (cur != null) {
                if (cur.v == u) {
                    degree++;
                    break;
                } else {
                    cur = cur.next;
                }
            }
        }
        return degree;
    }
}
